#include "quickSort.h"
#include "util.h"
#include "sortCommon.h"

static int _quickSortPartition(int a[], int lo, int hi)
{
    int i = lo, j = hi+1;
    int t = a[lo];

    while(1)
    {
        while(a[++i] < t)
        {
            if(i == hi)
                break;
        }
        while(t < a[--j])
        {
            if(j == lo)
                break;
        }

        if(i >= j)
            break;

        _exch(a, i, j);
    }

    _exch(a, lo, j);

    return j;
}

static void _quickSort(int a[], int lo, int hi)
{
   if(hi <= lo)
       return;
   int j;

   j = _quickSortPartition(a, lo, hi);
   _quickSort(a, lo, j-1);
   _quickSort(a, j+1, hi);
   UTIL_ASSERT(_is_range_sorted(a, lo, hi));
}

void quickSort(int a[], int n)
{
    UTIL_ASSERT(a != nullptr);
    UTIL_ASSERT(n >= 1);
    shuffle_array(a, n);

    _quickSort(a, 0, n-1);
    UTIL_ASSERT(_is_array_sorted(a, n));
}


